package 链表;

import java.util.HashMap;
import java.util.Map;

/**
 * 146. LRU 缓存
 *
 * 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
 * 实现 LRUCache 类：
 * LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
 * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 * void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
 * 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
 *
 * 解题思路：
 LRU（Least Recently Used）缓存是一种常见的缓存淘汰策略，当缓存达到容量上限时，它会优先淘汰最近最少使用的数据。为了实现LRU缓存，我们需要一个数据结构来支持以下操作：

 1. **快速查找**：能够快速查找缓存中是否存在某个键。
 2. **快速插入和删除**：当缓存满时，能够快速删除最近最少使用的数据，并插入新的数据。
 3. **快速更新**：当访问某个键时，能够快速将其标记为最近使用。

 为了实现这些操作，我们可以使用以下数据结构：

 - **哈希表（HashMap）**：用于快速查找键是否存在，并存储键值对。
 - **双向链表（Doubly Linked List）**：用于维护键的使用顺序，最近使用的键放在链表头部，最久未使用的键放在链表尾部。

 ### 具体步骤
 1. **定义双向链表节点**：每个节点包含键、值、前驱节点和后继节点。
 2. **初始化缓存**：设置缓存的容量，并初始化哈希表和双向链表。
 3. **实现`get`操作**：
 - 如果键存在于哈希表中，返回对应的值，并将该节点移动到链表头部（表示最近使用）。
 - 如果键不存在，返回`-1`。
 4. **实现`put`操作**：
 - 如果键已存在，更新值，并将该节点移动到链表头部。
 - 如果键不存在，插入新节点到链表头部，并更新哈希表。
 - 如果缓存已满，删除链表尾部的节点（最久未使用），并从哈希表中删除对应的键。
 */
public class L_146 {

    private Map<Integer, DLinkedNode> cache = new HashMap<>(); // 哈希表，用于快速查找
    private int size; // 缓存中实际的节点数量
    private int capacity; //容量
    private DLinkedNode head, tail; // 双向链表，用于维护键的使用顺序

    public L_146(int capacity) {
        this.size = 0;
        this.capacity = capacity;

        // 定义头尾节点
        head = new DLinkedNode();
        tail = new DLinkedNode();

        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        // 不存在
        if(node == null){
            return -1;
        }

        // 存在就将该节点移动到链表头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        // 先存Map中查询该节点
        DLinkedNode node = cache.get(key);
        // 该节点不存在
        if(node == null){
            // （1）没超过缓存
            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;
            // 添加到map 与 链表中
            cache.put(key, newNode);
            addNode(newNode);
            size++; // 实际容量大小计数
            // (2)超过缓存大小
            if(size > capacity){
                // 移除链表尾部节点（移除最近最少使用的节点）
                DLinkedNode tail = popTail();
                cache.remove(tail.key);
                size--;
            }
        }else { // 如果该节点存在
            // 如果键存在，就更新值，并将该节点移动到链表头部
            node.value = value;
            moveToHead(node);
        }
    }

    // 定义双向链表节点
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
    }

    // 添加节点到链表头部
    private void addNode(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;

        head.next.prev = node;
        head.next = node;
    }

    // 移除节点
    private void removeNode(DLinkedNode node) {
        // 找到当前节点的前驱与后继节点
        DLinkedNode prev = node.prev;
        DLinkedNode next = node.next;

        prev.next = next;
        next.prev = prev;
    }

    // 移动节点到链表头部
    private void moveToHead(DLinkedNode node){
        removeNode(node);
        addNode(node);
    }

    //移除链表尾部节点（移除最近最少使用的节点）
    private DLinkedNode popTail(){
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}
